As is generally known in the art, in distributed processing systems, users' data files are often distributed and replicated at multiple, geographically dispersed locations to reduce access time and to improve data availability in case of failure. Because a data file can be replicated at multiple locations, the distribution of replicated files must be synchronized. If these replicated files are not synchronized, then obsolete data may be inadvertently used by one of the multiple users. For this reason, those skilled in the art have directed a great deal of attention to providing concurrency control of these replicated data files.
There are several different methods of concurrency control. The simplest of these methods involves allowing users to continuously access replicated data stored at local servers and synchronizing the replicated files to periodically reconcile differences among the files. Of course, for heavily used multiple access systems like data records held by banking systems, which contain customer account information, etc., more stringent concurrency control measures (e.g. locking protocols) are necessary to avoid fraudulent activity or data interpretation errors.
Generally, any of these distributed network systems have multiple computing nodes (hereinafter nodes) placed at different locations. Each of these nodes has a database of some form (i.e. a collection of data files) and a processing capability. User data files can either be categorized as global data or non-global data. Global data files are referenced by all users, so they, by definition, are replicated, distributed and stored at each node in the entire network system. Non-global data files, however, are accessed only by a certain group of users and the files are stored only at selected nodes to meet the processing needs.
Typically, all nodes in a network can communicate and exchange data with each other over a communication system of some type, for example, an FDDI network, wide area packet-switching network, etc. When logging onto the system, users are normally connected to a specific node where they use data files, which are either global, non-global, or user specific.
Typically in a system with periodic updates, a pair of nodes sets up a synchronization session to identify and exchange updated copies of their common files. If a common file at only one of the nodes has been changed since the last synchronization, then the obsolete copy at the other node is replaced by the new one. If both copies have been updated, then the difference between them is stored along with original version of the file at both nodes. In this case, users are informed that two copies have been updated concurrently since the last synchronization and it is up to the user or a system administrator to resolve the update conflict. Each synchronization session is represented by the processing of a connection record that specifies the pair of nodes involved in the synchronization.
In any of these synchronization methods, there is some update delay of any one file. The update delay is defined as the time interval from the instant a file is updated at one node until the updated data becomes available in a replicated copy of the same file at another node. The maximum update delay is the longest update delay from any one node to all other nodes. Of course, it is important to minimize the maximum update delay by developing an efficient schedule for the synchronization sessions. As data files are expected to be updated continuously, data synchronization must take place repeatedly. Of course, the natural approach would be to synchronize the replication of the data files at a fixed, periodic schedule.
Since updated data can, and usually does, propagate from one node to another node via some intermediate nodes, the precedence relationship among the synchronization sessions needs to be maintained in order to achieve the targeted results. For example, for new data propagated from node A to node C via node B, the synchronization session between node A and node B should be completed before that between node B and C begins. Therefore, it is desirable to complete a synchronization session within the allocated time period with a very high probability. Unfortunately, the update delay is directly proportional to the time period allocated for each session. As a result, the time period for each session should be minimized while keeping the probability of a session exceeding the allotted time satisfactorily low at the engineered traffic load, i.e. in terms of update frequency and the amount of data to be exchanged among nodes. For most synchronization schemes, it is assumed that a fixed time period is allocated to all sessions, regardless of the pair of nodes involved and the amount of data exchanged during the synchronization period. Based on this assumption, usually the amount of time allocated for each session is referred to as session time.
Although a fixed session time is assumed here, the important point is to maintain precedence relationships among synchronization sessions. Thus, in the above example, node B may begin synchronizing with node C as soon as it is done synchronizing with node A.
An advanced multihop communication method, which is analogous in that nodes need to propagate updated data to all other nodes via some intermediate nodes in the data synchronization, and has been known in the art, is described in U.S. Pat. No. 4,914,648 issued to Acampora et al on Apr. 3, 1990 and entitled, "Multichannel, Multihop Lightwave Communication System," which is incorporated herein by reference. Briefly, this system enables users to communicate efficiently in multihop lightwave networks. The user nodes communicate with each other via intermediate nodes (i.e. multihop communication), including the change of wavelengths in case of wavelength multiplexing on a common optical fiber. The multihop lightwave communication network of Acampora et al allows packet concurrency in the network while avoiding the need for agile optical devices. The network comprises a lightwave communication medium which supports a number of independent user nodes and a plurality of N network interface units (NIUs). Each NIU is connected to the lightwave medium and one or more separate user nodes and comprises a transmitter section and a receiver section which are each fixedly assigned to transmit and receive, respectively, over a single channel or a plurality of separate channels to or from other NIUs of the network. In a connectivity pattern for the network of Acampora et al, the NIUs are divided into k groups of p.sup.k NIUs such that each NIU of a first group of p.sup.k NIUs is capable of transmitting over the fixed assigned single channel, or any or all of the p separate channels, to a preferred one or all of the associated p separate NIUs of a second group, etc. based on a generalization of a perfect shuffle pattern. This technique permits all NIUs of the network to communicate with all other NIUs either via a single hop or via multiple hops where NIUs in subsequent groups of p.sup.k NIUs act as intermediate retransmission units. This shuffle pattern has been termed "ShuffleNet" and provides full connectivity among nodes so that each user can communicate with all other users. Unfortunately, with this system, any time new nodes are added, the ShuffleNet pattern must be updated in the system. Therefore, because it is envisioned that future and even present day networks are constantly being updated with respect to the number of nodes on any one network, it is recognized that any synchronization system must be adaptable to this reality.
Moreover, it has been recognized in the art that any ideal solution to the data synchronization should also provide a low maximum update delay, an ability to withstand at least one node failure, and a minimal transfer of non-global data. Accordingly, there still exists a need in the art to provide an efficient, effective method to distribute and synchronize replicated data files. The present invention addresses such a need.